#include <atomic>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;

// 链表实现队列
typedef int DataType;
struct Node {
  DataType data;
  Node* next;
  Node(const DataType& d) {
    data = d;
    next = nullptr;
  }
};

class ListQueue {
 public:
  ListQueue() : head_(nullptr), tail_(nullptr) {}
  ~ListQueue() {
    int data;
    while (head_) {
      Dequeue(data);
    }
  }

  // 尾部入队
  void Enqueue(const DataType& data) {
    Node* node = new Node(data);
    if (tail_) {
      tail_->next = node;
    }
    tail_ = node;
    if (head_ == nullptr) head_ = node;
  }

  // 头部出队
  bool Dequeue(DataType& data) {
    if (head_ == nullptr) return false;
    if (head_->next == nullptr) {
      data = head_->data;
      delete head_;
      head_ = tail_ = nullptr;
    } else {
      Node* todel = head_;
      data = todel->data;
      head_ = head_->next;
      delete todel;
    }
    return true;
  }

  void Print() {
    Node* p = head_;
    while (p) {
      cout << p->data << ' ';
      p = p->next;
    }
    cout << endl;
  }

 private:
  Node* head_;
  Node* tail_;
};

void TestListQueue() {
  ListQueue queue;
  queue.Enqueue(1);
  queue.Enqueue(2);
  queue.Enqueue(3);
  queue.Enqueue(4);
  queue.Print();
  int data;
  while (queue.Dequeue(data)) {
    cout << data << ',';
  }
  cout << endl;
}

// 数组实现循环队列（基于CAS原子操作控制并发）（无锁并发队列）
// 可以百度“无锁队列”
template <typename T>
class LoopQueue {
 public:
  LoopQueue(int max_size) : max_size_(max_size), head_(0), tail_(0) {
    vec_.resize(max_size_);
  }
  ~LoopQueue() {}

  // 入队
  bool Enqueue(const T& data) {
    if ((tail_ + 1) % max_size_ == head_) return false;
    // int old_tail = tail_;  // 要CAS设置两个数据，怎么实现？
    vec_[tail_] = data;
    // std::atomic_compare_exchange_weak(&tail_, &old_tail,
    //                                   (old_tail + 1) % max_size_);
    tail_ = (tail_ + 1) % max_size_;
    return true;
  }

  // 出队
  bool Dequeue(T& data) {
    if (tail_ == head_) return false;
    data = vec_[head_];
    head_ = (head_ + 1) % max_size_;
    return true;
  }

  // 打印
  void Print() {
    for (int i = head_; i != tail_; ++i) {
      if (i == max_size_) i = 0;
      cout << vec_[i] << ' ';
    }
    cout << endl;
  }

 private:
  int max_size_;
  std::atomic<int> head_;
  std::atomic<int> tail_;
  std::vector<T> vec_;
};

void TestLoopQueue() {
  LoopQueue<int> queue(10);
  for (int i = 0; i < 10; ++i) {
    queue.Enqueue(i);
  }
  queue.Print();
  for (int i = 0; i < 5; ++i) {
    int out;
    if (queue.Dequeue(out)) cout << "out:" << out << endl;
  }
  queue.Print();
  for (int i = 0; i < 10; ++i) {
    queue.Enqueue(i);
  }
  queue.Print();
}

int main() {
  TestListQueue();
  cout << "--------------\n";
  TestLoopQueue();
}